This invention relates to image processing and, more particularly, to computing an Euler number for an image.
Image processing refers to the analysis and manipulation of images using a computer. The discipline encompasses a wide array of techniques, including pattern recognition and other image analysis, compression and encoding, such as for image transmission, and image construction, to name but a few examples. Image processing is used in diverse fields such as astronomy, medicine, military operations, communications, geology, meteorology and so on.
A binary or digital image is typically represented by one or more topological properties. Topological properties represent the geometric shape of the image. Where changes are made to the image itself, such as stretching, deformation, rotation, scaling, translation, or other rubber-sheet transformations, the topological properties do not change. These properties, therefore, are quite useful in image characterization. Topological properties, for example, may be helpful in performing shape matching, object and pattern recognition, image data retrieval, and so on.
One topological property of a digital image is known as an Euler number. An Euler number is defined as the difference between the number of connected components of the binary image and the number of holes in the image. Like the other topological properties, the Euler number remains invariant despite the above-mentioned transformation of the binary image.
For some classes of digital images, Euler numbers have strong discriminatory power. In other words, once the Euler number for a particular digital image is known, the digital image may readily be distinguished from other digital images in its class. This implies that the Euler number may be used for more efficient searching or matching of digital images.
For example, the Euler number may be used in medical diagnosis such as the detection of malaria infected cells. By calculating the Euler number of each cell image, the malaria infected cells may be identified, as the Euler number of an infected cell is often different from that of an uninfected cell. The Euler number may also be used for image searching, such as in a database of logo images. Critical image processing applications such as these involve large amounts of data and, at the same time, expect quick real-time response. Fast computation of the Euler number of an image, for some applications, is, therefore, an indispensable task.
Obtaining the Euler number for a digital image, however, may be computationally expensive. For a pixel matrix including 150,000 pixels, for example, over 300,000 pixel accesses and 50,000 or more processor cycles may be expected in computing the Euler number.
Thus, there is a continuing need for better ways to compute the Euler number for a binary image.